题目分析

这个题目看到关键字，计算多个元素最小值的最大值。看到这句话一定要想到二分答案。

二分查找

先排序，因为任意两种糖果的甜蜜度绝对差就是排序后的后一个糖果减去前一个糖果的甜蜜度差值。

二分答案，答案的最小值肯定是0，答案的最大值是(max - min) / (k - 1)，其中max是最大元素的值，min是最小元素的值。

上述公式是容易理解的，相当于在[min, max]中间插入隔板，肯定是均匀插入隔板，才能使任意两个隔板距离最小值最大。

我们然后要确定一点，最小的甜蜜度是一定要选择的。如果答案不选择最小的甜蜜度，假设选择的最小甜蜜度为x，倒数第二小的甜蜜度为y，那么y - x一定大于等于ans，如果选择最小的甜蜜度，y - min也必然大于等于ans。因此最小值(min)代替当前选择的最小值(x)也是不会出现问题的。

所以我们先选择最小值，二分查找ans，看选择mid = (left + right + 1) / 2是否满足条件。如果满足，那么可以在[mid, right]中继续二分，在[left, mid - 1]中二分。

从最小值开始，当前值为mid，查找数组中大于等于min + mid的第一个元素，表示该值一定要选择。原因和选择最小值是相同的。如果满足条件，那么尽量选择小的就行了。这样可以给后面的选择多一些空间。

如果选出了k个糖果，那么是满足条件的，否则是不满足条件的。

算法的时间复杂度为O(nlog(n))，空间复杂度为O(1)。

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        int n = price.size();
        sort(price.begin(), price.end());
        int mini = price[0], maxi = price[n - 1];
        int left = 0, right = (maxi - mini) / (k - 1);
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            int cur = mini;
            int idx = 0;
            for (int i = 0; i < k - 1; i++) {
                cur += mid;
                while (idx < n && price[idx] < cur) {
                    idx++;
                }
                if (idx < n) {
                    cur = price[idx];
                }
            }
            if (cur > maxi) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
};

刷题总结

这个题目思路容易想，还是记住关键点，多个最小值的最大值，或者多个最大值的最小值，一定要想到二分查找。